1. Field of the Invention
The invention relates to programmable logic devices ("PLD's"), and more particularly, to PLD's which implement an EXCLUSIVE OR function.
2. Description of the Prior Art
PLD's are well known and widely used in the field of semiconductor digital integrated circuits. A PLD generally includes multiple arrays of AND gates and OR gates interconnected in various combinations. The devices contain gates which are connected by fixed connections and gates which are connected by electrically programmable connections, such as fuses. The AND gates implement the boolean logic "AND" function to provide the product of selected inputs while the OR gates implement the boolean logic "OR" function to provide the sum of selected inputs. An OR gate whose inputs are the outputs of a plurality of AND gates implements the boolean Sum of Products function. Given enough products, often referred to for convenience as "p-terms", the sum of the products can express all boolean transfer functions.
The range of intended applications for the device influences the number of gates in the arrays, their layout, and how they are interconnected by the fixed and programmable connections. Such devices are highly useful because they enable the manufacturer or the end user, all within a single device design, to implement a large variety of boolean logic functions through programming of the programmable connections interconnecting the various AND gates and OR gates.
It is desirable in many applications to implement an EXCLUSIVE OR ("XOR") function in such a device. The EXCLUSIVE OR function is needed, for example, in arithmetic and parity generation circuits. As known from boolean logic equations, this function may be implemented programmably in a device having an array of programmable AND gates and an OR gate arranged to implement a Sum of Products, such as with an AND array feeding a fixed OR gate. In practice, however, this takes up an excessive number of product terms (AND gates). Implementing an EXCLUSIVE OR function that is N-bits wide (N inputs) requires 2.sup.N-1 programmable product terms to implement. For example, an EXCLUSIVE OR with five (5) inputs requires sixteen (16) product terms (programmable AND gates) to implement in this manner. An EXCLUSIVE OR function of three inputs A, B, C requires four (4) product terms and is written in sum of products notation as: ##EQU1## where "&" denotes the logical AND,
"#" denotes the logical OR, and PA1 "!" denotes the inverse of a variable.
FIG. 1 illustrates the implementation of the above three-wide XOR function with AND and OR gates.
Alternatively, it is known to include a so-called silicon XOR (hereinafter referred to as "fixed EXCLUSIVE OR" or "fixed XOR") in the output path of a PLD. A fixed XOR is made up of a combination of AND and OR gates non-programmably connected to each other. One example of a fixed XOR is shown in FIG. 2 and includes two AND gates 1, 2 each having an output feeding a respective input of OR gate 3. The AND gate 2 receives the input signal A and the inverse of input signal B while AND gate 1 receives the inverse of input signal A and the non-inverted input signal B. The output signal A *xor* B is then the logical EXCLUSIVE OR of the two input signals A, B. It should be noted that fixed XOR gates may be constructed in other ways known in the art, several of which are described in the text: Jacob Milman, Micro-electronics, at pages 133-34, McGraw Hill, Inc., New York, N.Y.
One known PLD having a fixed XOR is shown in FIG. 3 and includes a full Sum of Products branch 11 on the first input 15 and a single product term 7 as the second input 14 to the fixed XOR 16. The Sum of Products branch 11 includes a plurality of AND gates 8-1 through 8-M each having its OR output fed via a non-programmable connection to OR gate 9. Each AND gate is programmably connectable to each of a plurality of N inputs. The Sum of Products branch 11 connected to the first input 15 of the fixed XOR gate 16 may be programmed to implement an EXCLUSIVE OR function using boolean equations in addition to the fixed XOR 16. Eight (8) product terms (AND gates 8-1 . . . 8--8) from the Sum of Products branch 11 can be used to build a four (4) wide XOR which in turn propagates into the fixed XOR gate 16, making a total width of the implemented EXCLUSIVE OR function five (5) inputs wide. In comparison, as noted above, without the fixed XOR gate, the user would require sixteen (16) AND gates to implement a five (5) input EXCLUSIVE OR function.
U.S. Pat. No. 4,758,746 shows a PLD architecture with a plurality of logic cells, each having a fixed XOR, an OR gate and a number of product terms which can feed the OR gate and the fixed XOR. The disclosed architecture permits the product terms that are generated in the AND array of a first logic cell to be steered to a second logic cell, so that the OR and XOR gates of the second cell can use the product terms of the first cell. While providing some flexibility, product terms that are allocated to a given logic cell are stolen away from another cell. This limits the devices usefulness in implementing very wide EXCLUSIVE ORs.
It is an object of the invention to provide a PLD in which the number of product terms necessary to implement wide EXCLUSIVE OR's is reduced compared to the known devices.
It is another object of the invention to provide a PLD in which wide EXCLUSIVE ORs can be calculated in a shorter time than known devices.
It is another object of the invention to provide such a device which remains flexible to implement other boolean functions in an efficient manner in addition to implementing the EXCLUSIVE OR function.